package Leetcode.树.HAFUMAN2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Huffman树
 */


public class Huffman {
    private static final int[] a = {5,6,8,7,15};
    public static void main(String[] args) {
        Huffman huffman = new Huffman(a);
        huffman.print();


//        List<Integer> list = new ArrayList<>();
//        list.add(1);
//        list.add(2);
//        list.add(3);
//        list.add(4);
//        list.add(5);
//        for (int i = 0; i < list.size(); i++) {
//            if (i == 3) {
//                list.add(3, 100);
//            }
//
//        }

//        while (!list.isEmpty()) {
//            System.out.println(list.remove(0));
//
//        }
//        System.out.println("list= "+list);
    }

    private HuffmanNode mRoot;  // 根结点
    List<HuffmanNode> TreeList = new ArrayList<>();

    /* 
     * 创建Huffman树
     *
     * @param 权值数组
        将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
        在森林中选出根结点的权值最小的两棵树进行合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
        从森林中删除选取的两棵树，并将新树加入森林；
        重复(02)、(03)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

     */
    public Huffman(int a[]) {
        Arrays.sort(a);

        for (int i = 0; i < a.length; i++) {
            HuffmanNode node = new HuffmanNode(a[i], null, null, null);
            TreeList.add(node);
        }

        while (TreeList.size() > 1) {
            HuffmanNode left = TreeList.remove(0);
            HuffmanNode right = TreeList.remove(0);

            // 新建parent节点，左右孩子分别是left/right；
            // parent的大小是左右孩子之和
            HuffmanNode parent  = new HuffmanNode(left.key + right.key, left, right, null);
            left.parent = parent;
            right.parent = parent;

            insert(parent);
        }

        mRoot = TreeList.get(0);
    }

    private void insert(HuffmanNode parent) {
        boolean flag = false;
        for (int i = 0; i < TreeList.size(); i++) {
            if (TreeList.get(i).key >= parent.key) {
                TreeList.add(i, parent);
                flag = true;
                break;
            }
        }
        if (!flag) {
            TreeList.add(TreeList.size(), parent);
        }
    }

    private void print(HuffmanNode tree, int key, int direction) {

        if(tree != null) {

            if(direction==0)    // tree是根节点
                System.out.printf("%2d is root\n", tree.key);
            else                // tree是分支节点
                System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction==1?"right" : "left");

            print(tree.left, tree.key, -1);
            print(tree.right,tree.key,  1);
        }
    }

    public void print() {
        if (mRoot != null)
            print(mRoot, mRoot.key, 0);
    }

}